Звезда
| време | меморија | улаз | излаз |
|---|---|---|---|
| 0,3 s | 64 Mb | стандардни излаз | стандардни улаз |
Особа је звезда (енгл. superstar) у некој групи људи ако њу сви остали познају, а она не познаје никога. Написати програм који одређује да ли у датој групи људи постоји звезда и која је то особа. Иако је за учитавање података потребно време које квадратно зависи од броја присутних особа, алгоритам треба да ради у времену које линеарно зависи од броја особа.
Улаз
Са стандардног улаза се учитава број особа присутних на забави \(n\) (\(1 \leq n \leq 100\)), а затим матрица димензије \(n \times n\) која на позицији \((i, j)\) тј. у врсти \(i\) и колони \(j\) садржи 1 ако особа \(i\) познаје особу \(j\) тј. 0 ако је не познаје. На дијагонали матрице се налазе јединице (свака особа познаје саму себе).
Излаз
На стандардни излаз исписати редни број особе која је звезда, ако звезда постоји (особе се броје од \(0\) до \(n-1\)) или -1 ако звезда не постоји.
Пример
Улаз
3 1 1 0 0 1 0 1 1 1
Излаз
1
Објашњење
Особа на позицији 1 је звезда, јер она не познаје ни особу на позицији 0, ни особу на позицији 2 (у врсти 1 су све нуле, осим на позицији 1), а њу познају и особа на позицији 0 и особа на позицији 2 (у колони 1 су све јединице).
Морате бити улоговани како бисте послали задатак на евалуацију.